package 动态规划;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-14
 */
public class 最长无重复子串 {
    //1.通过左右指针
    public static String longestUnique(String str) {
        char[] arr = str.toCharArray();
        if (str.length() == 0) {
            return str;
        }
        int left = 0, right = 1;
        String max = arr[0] + "";
        while (right < str.length()) {
            char c = arr[right];
            String subStr = str.substring(left, right);
            int dupIndex = subStr.indexOf(c);
            if (dupIndex != -1) {
                left = dupIndex + 1+left;
                subStr = str.substring(left, right);
            }
            subStr = subStr + c;
            if (subStr.length() > max.length()) {
                max = subStr;
            }
            right++;
        }
        return max;
    }

    //2.通过map建立对应关系
    public static String longestUniqueMap(String str) {
        char[] arr = str.toCharArray();
        int k = 0;
        String max = arr[0] + "";
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            if (map.containsKey(ch)) {
                k = map.get(ch) + 1;
            }
            map.put(ch, i);
            String subStr = str.substring(k, i + 1);
            if (subStr.length() > max.length()) {
                max = subStr;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb"));
        System.out.println(longestUniqueMap("abcabcbb"));
    }
}
